package LinkedList;

/**
 *  题目 ：链表的中间节点
 *  题目详情 ：
 *  给定一个头结点为 head 的非空单链表，返回链表的中间结点。
 * 如果有两个中间结点，则返回第二个中间结点。
 */
public class P876 {
    public ListNode middleNode(ListNode head) {
        ListNode p1 = head;  // 慢指针
        ListNode p2 = head;  // 快指针
        while(p2.next != null){
//            System.out.println(p2.val);
            p1 = p1.next;
            p2 = p2.next;
            if (p2.next != null){   // 由于此处快指针只需要比慢指针多执行一次next，所以使用if判断语句进行判断
                p2 = p2.next;
            }
        }
        return p1;
    }
    /**
     *  思考 ：
     *  同时可以使得将p1，p2快慢指针指向 原链表的哨兵节点，
     *  同时需要设置一个标志位flag（用来判断原链表中的节点数为奇数还是偶数）
     *  （1）奇数 ：直接返回慢指针所指向的节点；
     *  （2）偶数 ：由于若有两个中间节点的话，需要返回第二个节点，所以，需要返回慢指针所指向节点的next节点；
     */
}
